perm filename LISPAD[1,JMC] blob
sn#005260 filedate 1970-06-16 generic text, type T, neo UTF8
00100 ON COMPUTING WITH SYMBOLIC EXPRESSIONS - A POSITION PAPER
00200
00300 by John McCarthy
00400
00500 I have been interested in computing with symbolic expressions
00600 since 1956 and started developing the LISP language for this purpose
00700 in 1959. The first version of LISP was working in the spring of
00800 1960, and LISP 1.5, the current LISP language, was working in 1962. A
00900 rather fancy version of LISP, intended to be all things to all men,
01000 was developed with ARPA support for the Q32 computer at SDC, but the
01100 system was never transferred to other computers for a combination of
01200 technical, political and financial reasons.
01300
01400 LISP has several essential characteristics and several
01500 inessential ones. Here are the essential characteristics:
01600
01700 1, Data are S-expressions which are represented internally by
01800 list structures. Other forms of data like numbers and arrays are
01900 provided, but the list structures are fundamental.
02000
02100 2. Programs may be expressed as functions defined by
02200 conditional expressions containing the function being defined. Other
02300 forms of program may also be provided.
02400
02500 3. A certain set of basic functions and predicates of
02600 symbolic expressions is provided.
02700
02800 4. The language itself is not dedicated to any particular
02900 kind of symbolic data such as algebraic expressions or formulas of
03000 logic.
03100
03200 5. Programs may be represented by S-expressions themselves
03300 although they also may have other representations.
03400
03500 Most present implementations of LISP also have the following
03600 inessential features:
03700
03800 1. Unless special input-output programs are written, as they
03900 often are, data are represented externally as S-expressions, and this
04000 is often awkward, especially when the data are lengthy.
04100
04200 2. Arithmetic in most versions of LISP is about 50 times
04300 slower than compiled FORTRAN making certain kinds of combined
04400 symbolic and numerical calculations awkward.
04500
04600 LISP has had the following rivals as a language for symbolic
04700 computation:
04800
04900 1. COMIT - This language is based on string rewriting rules.
05000 Since Yngve stopped promoting it, it seems to have died.
05100
05200 2. SNOBOL - Also based on string rewriting rules. It
05300 represents data as strings of characters. This is convenient for
05400 input-output but is essentially slower than representation by list
05500 structure for internal computations. SNOBOL is very much alive and
05600 is maintained by several groups, but mainly at Bell Labs. I don`t
05700 know of any very large computation jobs done in SNOBOL but there
05800 probably are some.
05900
06000 3.SLIP - This is a set of FORTRAN routines for list
06100 processing. I think it is defunct.
06200
06300 4. POP-2 - A rather elegant generalization of LISP 1.5
06400 developed and used at the University of Edinburgh. Available only as
06500 an interpreter.
06600
06700 5. ALPAK - A system of machine language routines for the
06800 manipulation of polynomials and rational functions. It is reputed to
06900 be quite fast for the specialized tasks for which it is suitable.
07000
07100 6. Formula Algol - This language represents Algol expressions
07200 by list structure, and allows the same Algol formula to have either a
07300 symbolic or a numerical interpretation according to the types of the
07400 variables. In my opinion this is ingenious but unsoundly tricky.
07500
07600 7. FORMAC - This system for the manipulation of the formulas
07700 of ordinary mathematics has had wide use. It has preferred forms of
07800 algebraic simplification built into its operators for formula
07900 addition, multiplication, differentiation, etc. In my opinion, this
08000 is a mistake because the preferred form of simplification is quite
08100 problem dependent. FORMAC has received widespread use perhaps partly
08200 due to its sponsorship by IBM.
08300
08400 8. REDUCE - This is a package within LISP 1.5 for
08500 manipulation and human controlled simplification of algebraic
08600 expressions, especially polynomials in many variables.
08700
08800 9. FLIP - This is a format directed computation system within
08900 LISP 1.5 developed at BBN.
09000
09100 In the above survey, I have included only systems that have
09200 achieved substantial use by groups other than the designers of the
09300 system. There have been innumerable languages that have either not
09400 been used at all or only used by their designers.
09500
09600 The history of symbolic computation has been very spotty.
09700 Much more effort has gone into implementing systems of symbolic
09800 computation than into using them. There are few uses for very large
09900 symbolic computations, and the use of computers for small symbolic
10000 computations really depends on the availability of good display based
10100 time-sharing systems to people who do a lot of symbolic computation.
10200 The history of large symbolic calculations as far as I know is about
10300 as follows:
10400
10500 1. Toy symbolic computations begin with Lanning and Zierler
10600 who wrote differentiation routines for Whirlwind.
10700
10800 2. LISP was originally developed with algebraic computations
10900 in mind, and toy programs for differentiation and algebraic
11000 simplification were done immediately.
11100
11200 3. The first substantial symbolic computation was probably
11300 Slagle's symbolic integration program , but Slagle's goal was in
11400 artificial intelligence rathere than in symbolic computation itself.
11500
11600 4. Many theorem proving programs have been done in LISP and
11700 in other languages.
11800
11900 5. Probably the first, and perhaps the only production
12000 symbolic computations on a production basis are Hearn's physics
12100 computation using REDUCE. One physicist told me that Hearn and his
12200 FORTRAN competitor in Europe can just about satisfy the world demand
12300 for Feynman diagram computation of matrix elements.
12400
12500 On the basis of this admittedly sketchy information, I would
12600 draw the following conclusions:
12700
12800 1.The present symbolic computation languages are apparently
12900 adequate for the kinds of symbolic computations actually being done.
13000 In particular, we have not seen any problems for which LISP is
13100 obviously inadequate, especially if some tinkering is allowed.
13200
13300 2. My previous efforts to promote symbolic computation at
13400 Stanford met with only one major success, namely Hearn. I attribute
13500 this to lack of demand for large computations. I am eager to try
13600 again if there is genuine demand.
13700
13800 3. The last thing we need is another effort to make a new
13900 language without experience of pushing existing languages to their
14000 limit.
14100
14200 4. It is clear that new systems will eventually be required.
14300 Many kinds of data processing benefit from data structures not
14400 provided for in present languages. Therefore, programs requiring
14500 very fast sysmbolic computation are often written in machine
14600 language. However, if the reason for the speed requirement is to
14700 mitigate the effect of a combinatorial explosion, LISP and other
14800 symbolic computation languages often win out over machine languages
14900 because more elaborate heuristics for avoiding the explosion can be
15000 written and debugged in a given time.
15100
15200 The following kinds of improvements in LISP are contemplated:
15300
15400 1. An improvement of Quam's system permitting input and
15500 output of expressions in an arbitrary syntax.
15600
15700 2. Fast numerical computations.
15800
15900 3. A standard system of syntax directed computation.
16000
16100 4. A better input language for LISP programs along the lines
16200 of Colby's MLISP.
16300
16400 5. Many operating improvements to the on-line interaction
16500 with users and the PDP-10 time-sharing system.